#include<vector>
#include<algorithm>
using std::min;
using std::max;
using std::vector;


class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        int maxL = 0;
        for (int i = 0; i < matrix.size(); i++) {
            dp[i][0] = matrix[i][0] - '0';
            maxL = max(maxL, dp[i][0]);
            
        }
        for (int j = 1; j < matrix[0].size(); j++) {
            dp[0][j] = matrix[0][j] - '0';
            maxL = max(maxL, dp[0][j]);
        }
        for (int i = 1; i < matrix.size(); i++) {
            for (int j = 1; j < matrix[0].size(); j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    maxL = max(maxL, dp[i][j]);
                    }
            }
        }
        return maxL * maxL;
    }
};